package com.xy6.algo.search;

/**
 * 二叉排序树查找
 * <p>时间复杂度：O(log2^n)
 * 
 * <pre>
 * 根据集合，构建一个二叉排序树，然后进行查找。
 * 二叉排序树：左子节点<根节点<右子节点。
 * 
 * 最坏情况，效率为O(n)。
 * 改进版：平衡查找树，如2-3查找树，一种实现：红黑树，另一个扩展：B/B+树
 * </pre>
 * 
 * @author zhang
 * @since 2017-08-14
 */
public class SearchBinaryTree<T extends Comparable<? super T>> {

	/**
	 * 节点数据结构
	 * 
	 * @author zhang
	 *
	 * @param <T>
	 */
	static class BinaryNode<T> {
		T data;

		BinaryNode<T> left;

		BinaryNode<T> right;

		public BinaryNode() {
			data = null;
			this.left = null;
			this.right = null;
		}

		public BinaryNode(T data) {
			this(data, null, null);
		}

		public BinaryNode(T data, BinaryNode<T> left, BinaryNode<T> right) {
			this.data = data;
			this.left = left;
			this.right = right;
		}
	}

	public BinaryNode<T> rootTree;
	
	/**
	 * 构造一棵空的二叉查找树
	 */
	public SearchBinaryTree(){
		rootTree = null;
	}
	
	/**
	 * 清空
	 */
	public void clear(){
		rootTree = null;
	}

	public boolean isEmpty() {
		return this.rootTree == null;
	}
	
	/**
	 * 查找指定的元素，默认从根节点开始查找
	 * 
	 * @param t
	 * @return
	 */
	public boolean contains(T t) {
		return contains(t, rootTree);
	}

	/**
	 * 从某个节点处开始查找元素
	 * 
	 * @param t
	 * @param node
	 * @return
	 */
	public boolean contains(T t, BinaryNode<T> node) {
		if (node == null) {
			return false;
		}
		int result = t.compareTo(node.data);
		if (result > 0) {
			return contains(t, node.right);
		} else if (result < 0) {
			return contains(t, node.left);
		} else {
			return true;
		}
	}

	/**
	 * 插入元素
	 * 
	 * @param t
	 */
	public void insert(T t) {
		rootTree = insert(t, rootTree);
	}

	public BinaryNode<T> insert(T t, BinaryNode<T> node) {
		if (node == null) {
			return new BinaryNode<T>(t, null, null);
		}
		int result = t.compareTo(node.data);
		if (result < 0) {
			node.left = insert(t, node.left);
		} else if (result > 0) {
			node.right = insert(t, node.right);
		}
		return node;
	}

	/**
	 * 查找二叉树中最小值
	 * 
	 * @return
	 */
	public T findMin() {
		if (isEmpty()) {
			System.out.println("二叉树为空");
			return null;
		} else {
			return findMin(rootTree).data;
		}
	}

	/**
	 * 查找二叉树中最大值
	 * 
	 * @return
	 */
	public T findMax() {
		if (isEmpty()) {
			System.out.println("二叉树为空");
			return null;
		} else {
			return findMax(rootTree).data;
		}
	}

	/**
	 * 查找二叉树中最小值所在的节点
	 * 
	 * @param node
	 * @return
	 */
	public BinaryNode<T> findMin(BinaryNode<T> node) {
		if (node == null) {
			return null;
		} else if (node.left == null) {
			return node;
		} else {
			return findMin(node.left);
		}
	}

	/**
	 * 查找二叉树中最大值所在的节点
	 * 
	 * @param node
	 * @return
	 */
	public BinaryNode<T> findMax(BinaryNode<T> node) {
		if (node == null) {
			return null;
		}
		while (node.right != null) {
			node = node.right;
		}
		return node;
	}

	public void remove(T t) {
		rootTree = remove(t, rootTree);
	}

	public BinaryNode<T> remove(T t, BinaryNode<T> node) {
		if (node == null) {
			return node;
		}
		int result = t.compareTo(node.data);
		if (result > 0) {
			node.right = remove(t, node.right);
		} else if (result < 0) {
			node.left = remove(t, node.left);
		} else if (node.left != null && node.right != null) {
			node.data = findMin(node.right).data;
			node.right = remove(node.data, node.right);
		} else {
			node = (node.left != null) ? node.left : node.right;
		}
		return node;
	}
	
	/**
	 * 先序遍历
	 * <p>先访问根，然后访问子树
	 * 
	 * @param node
	 */
	public void preOrder(BinaryNode<T> node){
		if(node != null){
			System.out.print(node.data + " ");
			preOrder(node.left);
			preOrder(node.right);
		}
	}
	
	/**
	 * 中序遍历
	 * <p>先访问左子树，再访问根，再访问右子树
	 * 
	 * @param node
	 */
	public void inOrder(BinaryNode<T> node){
		if(node != null){
			inOrder(node.left);
			System.out.print(node.data + " ");
			inOrder(node.right);
		}
	}

	public static void main(String[] args) {
		testSort();
	}

	public static BinaryNode<Integer> init(){
		BinaryNode<Integer> node3 = new BinaryNode<>(3);
		BinaryNode<Integer> node1 = new BinaryNode<>(1);
		BinaryNode<Integer> node4 = new BinaryNode<>(4, node3, null);
		BinaryNode<Integer> node2 = new BinaryNode<>(2, node1, node4);
		BinaryNode<Integer> node8 = new BinaryNode<>(8);
		BinaryNode<Integer> root = new BinaryNode<>(6, node2, node8);
		
		return root;
	}
	
	public static void test1(){
		SearchBinaryTree<Integer> tree = new SearchBinaryTree<>(); 
		tree.rootTree = init();
		tree.preOrder(tree.rootTree);
		System.out.println();
		tree.remove(4);
		tree.preOrder(tree.rootTree);
	}
	
	/**
	 * 根据数组构建一个二叉排序树，并按升序输出
	 */
	public static void testSort(){
		Integer[] arr = new Integer[]{1, 3, 5, 2, 4, 6};
		SearchBinaryTree<Integer> tree = new SearchBinaryTree<>(); 
		for (int i = 0; i < arr.length; i++) {
			tree.insert(arr[i]);
			tree.inOrder(tree.rootTree);
			System.out.println();
		}
		System.out.println(tree.contains(4));
	}
	
}
